package com.markus.code.排序.base;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/4 18:29
 * todo:
 */
public class QuickSort {
    /**
     * 快排1.0版本,每次都指定左边的元素为中间值，比较每个值与这个中间值的大小，
     * 大于中间值的放在数组的左边，等于中间值的放在数组的中间，大于中间值的放在数组的右边
     * 1.0版本，时间复杂度为O(n^2)
     */
    public static void quickSort_1(int []arr,int L,int R){
        if (L >= R){
            return ;
        }
        int partition = arr[R];
        int less = L-1;
        int more = R+1;
        int left = L;
        while(left < more){
            if (arr[left] > partition){
                swap(arr,left,--more);
            }else if (arr[left] == partition){
                left++;
            }else{
                swap(arr,left++,++less);
            }
        }
        quickSort_1(arr,L,less);
        quickSort_1(arr,more,R);
    }

    public static void quickSort_2(int []arr,int L,int R){
        if (L < R){
            int index = L+(int) ((R-L+1)*Math.random());
            int partition = arr[index];
            int[] partition1 = partition(arr, L, R, partition);
            quickSort_1(arr,L,partition1[0]-1);
            quickSort_1(arr,partition1[1]+1,R);
        }
    }

    public static int[] partition(int []arr,int L,int R,int partition){
        int less = L-1;
        int more = R+1;
        int left = L;
        while (left < more) {
            if (arr[left] < partition){
                swap(arr,left++,++less);
            }else if (arr[left] == partition){
                left++;
            }else{
                swap(arr,left,--more);
            }
        }
        return new int[]{less+1,more-1};
    }
    private static void swap(int []arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int []arr = {3,6,4,7,1,8,1,5,5,9,6};
        quickSort_1(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
        int []arr1 = {3,6,4,7,1,8,1,5,5,9,6};
        quickSort_2(arr1,0,arr1.length-1);
        for (int i : arr1) {
            System.out.print(i+" ");
        }
    }
}
